package com.liang.leetcode.list;

/**
 * 24.两两交换链表中的节点
 * <a href="https://leetcode-cn.com/problems/swap-nodes-in-pairs/">https://leetcode-cn.com/problems/swap-nodes-in-pairs/</a>
 * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
 */
public class List04_SwapPairs {
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};
        ListNode head = ListNodeUtil.createLinkedList(nums);
        head = swapPairs(head);
        ListNodeUtil.printLinkedList(head);
    }

    /**
     * 交换链表中的每对节点。
     * 本函数通过创建一个虚拟节点dummyNode来简化链表操作，避免了处理链表头节点特殊情况的需要。
     * 使用cur指针来追踪当前操作的节点，通过不断地交换每对节点来达到目的。
     * @param head 链表的头节点。
     * @return 交换后的链表的头节点。
     */
    public static ListNode swapPairs(ListNode head) {
        // 创建一个虚拟头结点，next指向第一个存储元素的节点，避免链表为空的情况
        ListNode dummyNode = new ListNode(0, head);
        // cur 指向虚拟头结点
        ListNode cur = dummyNode;

        while (cur.next != null && cur.next.next != null) {
            // 指向需要交换的两个结点
            ListNode node1 = cur.next;
            ListNode node2 = cur.next.next;
            // 临时结点，保存两个结点后面的结点
            ListNode temp = cur.next.next.next;

            // 步骤一：dummyNode指向交换后的头结点
            cur.next = node2;
            // 步骤二
            node2.next = node1;
            // 步骤三
            node1.next = temp;
            // 更新 cur, cur 需要指向反转结点的前一个结点才能操作后面的结点
            // cur 指向node1 是因为 node1 和 node2 已经交换位置了
            cur = node1;
        }
        // 返回链表的头结点
        return dummyNode.next;
    }

    // 将步骤 2,3 交换顺序，这样不用定义 temp 节点
    public static ListNode swapPairs2(ListNode head) {
        // 虚拟头结点，避免链表为空的情况
        ListNode dummyHead = new ListNode(0, head);
        ListNode cur = dummyHead;

        while (cur.next != null && cur.next.next != null) {
            ListNode node1 = cur.next; // 当前对中的第一个节点
            ListNode node2 = cur.next.next; // 当前对中的第二个节点

            cur.next = node2;  // 步骤 1
            node1.next = node2.next;  // 步骤 3
            node2.next = node1;  // 步骤 2

            // 将当前节点更新为下一个待交换的对的起始节点
            cur = cur.next.next;
        }

        // 返回交换后的链表的头节点
        return dummyHead.next;
    }

    /**
     * 递归地交换链表中的每对节点。
     * @param head 链表的头节点，链表是一个单向链表，每个节点包含一个整数值。
     * @return 返回交换后的链表的头节点。
     */
    // 递归
    public static ListNode swapPairs3(ListNode head) {
        /**
         * 如果链表为空或只有一个节点，则无需交换，直接返回头节点。
         * 这是递归的终止条件。
         */
        if (head == null || head.next == null) return head;

        // 获取当前节点的下一个节点，用于后续的交换操作。
        // 获取当前节点的下一个节点
        ListNode next = head.next;

        // 递归调用交换函数，对下一个节点的下一节点开始的子链表进行交换。
        // 这里是递归的关键，它会先处理更远端的节点对，再回来处理当前节点对。
        // 进行递归
        ListNode newNode = swapPairs3(next.next);

        // 将当前节点的下一节点指向当前节点，完成节点对的交换。
        // 这里进行交换
        next.next = head;

        // 将当前节点指向递归返回的新节点，完成节点对的连接。
        head.next = newNode;

        // 返回交换后的链表的头节点，由于每对节点交换后，原来的第二个节点变成了新的头节点，所以返回next。
        return next;
    }
}
